package com.example.algorithm.service.impl;

import com.example.algorithm.service.DynamicPlanService;
import org.springframework.stereotype.Service;

import java.util.*;

/**动态规划
 * 1)定义子问题
 * 2)写出子问题的递推关系
 * 3)确定 DP 数组的计算顺序
 * 4)空间优化（可选）
 *
 * @author Administrator
 * @date 2024/7/31 14:07
 * @description
 */
@Service
public class DynamicPlanServiceImpl implements DynamicPlanService {
    /**
     * 斐波那契数是一种非常有趣的数列，其每个数字都是前两个数字的和
     * 解题思路：
     * 构造数组dp
     * 1.状态表示 : dp[i] 就是第 i 个泰波那契数
     * 2.状态转移方程 : dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
     * 3.初始化是为了填表的时候不越界访问,dp[0] = 0, dp[1] = dp[2] = 1
     * 4.填表顺序 从左往右
     * 5.返回值  dp[N]
     * @param n
     * @return
     */
    @Override
    public int fibonacci(int n) {
        int dp[] = new int[n+1];
        if(n<2){
            return n;
        }
        if(n==2){
            return 1;
        }
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;
        for(int i=3;i<=n;i++){
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }

    /**NO.78 爬楼梯
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     *
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * @param n
     * @return
     * 解法一：动态规划
     * 解法二：矩阵快速幂
     * 解法三：通项公式
     *
     */
    @Override
    public int climbStairs(int n) {
        int dp[] = new int[n+1];
        if(n<=2){
            return n;
        }
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }

        return dp[n];
    }

    /**NO.79 杨辉三角
     * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
     *
     * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
     * @param numRows
     * @return
     * 解法一：数学
     * 解法二：动态规划
     */
    @Override
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i<numRows;i++){
            List<Integer> tmp = new ArrayList<>();
            tmp.add(1);
            for(int j=1;j<i;j++){
                tmp.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));
            }
            if(i!=0){
                tmp.add(1);
            }
            res.add(tmp);
        }
        return res;
    }

    /**NO.80 打家劫舍
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     *
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
     * @param nums
     * @return
     * 解法一：动态规划
     * 解法二：滚动数组
     *
     */
    @Override
    public int rob(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }
        if(nums.length==2){
            return Math.max(nums[0],nums[1]);
        }
        int dp[] = new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<dp.length;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[dp.length-1];
    }

    /**NO.81 完全平方数
     * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
     *
     * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
     * @param n
     * @return
     * 解法一：动态规划
     * 解法二：数学【四平方和定理】
     * 解法三：bfs
     * 解法四：完全背包
     *
     */
    @Override
    public int numSquares(int n) {
        int dp[] = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        int max = (int)Math.sqrt(n);
        for (int i=0;i<=max;i++){
            int weight=i*i;
            for(int j=weight;j<=n;j++){
               if(dp[j-weight]!=Integer.MAX_VALUE){
                   dp[j]=Math.min( dp[j],(dp[j-weight]+1));
               }
            }

        }
        return dp[n];
    }

    /**NO.82 零钱兑换
     * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
     *
     * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
     *
     * 你可以认为每种硬币的数量是无限的。
     *  dp[j]=Math.min( dp[j],dp[j-1]+1);
     * @param coins
     * @param amount
     * @return
     * 解法一：记忆化搜索(背包)
     * 解法二：动态规划
     * 解法三：贪心算法
     *
     */
    @Override
    public int coinChange(int[] coins, int amount) {
        int dp[] = new int[amount+1];
        Arrays.fill(dp,amount+1);
        if(coins.length==0){
            return -1;
        }
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            for(int coin:coins){
                if(i>=coin){
                    dp[i]=Math.min( dp[i],dp[i-coin]+1);
                }


            }
        }
        return  dp[amount]>amount?-1:dp[amount];
    }
    /**NO.83 单词拆分
     * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
     *
     * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
     * @param s
     * @param wordDict
     * @return
     * 解法一：动态规划
     * 解法二：记忆化回溯
     * 解法三：dfs
     * 解法四：bfs
     * 解法五：背包问题
     */
    @Override
    public boolean wordBreak(String s, List<String> wordDict) {
        if(s.length()==0){
            return false;
        }
        boolean [] dp = new boolean[s.length()+1];
        Arrays.fill(dp,false);
        dp[0]=true;
        for(int i=0;i<=s.length();i++){
            if (!dp[i]) {
                continue;
            }
            for(String word:wordDict){
               if(word.length()+i<=s.length()&&s.startsWith(word,i)){
                   dp[i+word.length()]=true;
               }
            }

        }

        return dp[s.length()];
    }

    /**NO.84 最长递增子序列
     * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
     *
     * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
     * 子序列
     * 。
     * @param nums
     * @return
     * 解法一：动态规划
     * 解法二：贪心二分查找
     * 解法三：记忆化搜索
     *
     */
    @Override
    public int lengthOfLIS(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int dp[] = new int[nums.length];
        dp[0]=1;
        int maxLength = 1;
        for(int i=1;i<nums.length;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            maxLength = Math.max(maxLength,dp[i]);
        }

        return maxLength;
    }

    /**NO.85 乘积最大子数组
     * 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
     * 子数组
     * （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
     *
     * 测试用例的答案是一个 32-位 整数。
     * @param nums
     * @return
     * 解法一：动态规划
     *
     */
    @Override
    public int maxProduct(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        long max = nums[0];
        long min = nums[0];
        long maxProduct=nums[0];
        for(int i=1;i<nums.length;i++){
            long maxTemp= max,minTemp=min;
            max=Math.max(nums[i],Math.max(maxTemp*nums[i],minTemp*nums[i]));
            min=Math.min(nums[i],Math.min(maxTemp*nums[i],minTemp*nums[i]));
            if (min < (-1 << 31)) {
                min = nums[i];
            }
            maxProduct = Math.max(maxProduct,max);
        }
        return (int)maxProduct;
    }

    /**NO.86 分割等和子集
     * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     * @param nums
     * @return
     * 解法一：动态规划(0-1背包)
     *
     */
    @Override
    public boolean canPartition(int[] nums) {
        if(nums.length==0){
            return false;
        }
        int sum=0;
        for(int num:nums){
            sum+=num;
        }
        if(sum%2!=0){
            return false;
        }
        int target = sum/2;
        int []dp = new int[target+1];
        for(int i=0;i<nums.length;i++){
            for(int j=target;j>=nums[i];j--){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }

        }
        return dp[target]==target;
    }

    /**NO.87 最长有效括号
     * 难度：困难
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号
     * 子串
     * 的长度。
     * @param s
     * @return
     * 解法一：动态规划
     * 解法二：栈
     * 解法三：不需要额外空间，符号计数(贪心)
     *
     */
    @Override
    public int longestValidParentheses(String s) {
        if(s.length()<2){
            return 0;
        }
        int dp[] = new int[s.length()];
        dp[0]=0;
        int max =0;
        for(int i=1;i<s.length();i++){
            if(s.charAt(i)==')'){
                if(s.charAt(i-1)=='('){
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }else if(i - dp[i - 1] > 0 &&s.charAt(i-dp[i-1]-1)=='('){
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
            }

            max = Math.max(max,dp[i]);
        }
        return max;
    }
}
